package ailibaba.number1;

import java.util.*;

/**
 * 题目网页
 * https://www.nowcoder.com/test/question/a55198d2e65746009110226f2f6c8533?pid=30440638&tid=53650797
 *
 * @Author Jun jie Yi
 * @Date 2022/3/15 22:32
 */
public class SonSet {

    private static List<Integer> tmpArr = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //int T = 2;
        int T = scanner.nextInt();
        System.out.println(T);
        //int[] n = {3, 4};
        int[] n = new int[T];
        for (int i = 0; i < n.length; i++) {
            n[i] = scanner.nextInt();
            System.out.println(n[i]);


        }
        List<Integer[][]> l = new LinkedList<>();
        Integer[][] n1 = {{1, 3, 2}, {0, 2, 3}};
        Integer[][] n2 = {{1, 5, 4, 2}, {10, 32, 19, 21}};
        l.add(n1);
        l.add(n2);
        //调用解决问题的方法
        solution(T, n, l);
    }

    /**
     * @param T       组数
     * @param array_n 每组 x 的个数和 y 的个数
     * @param list_xy x 和 y 具体的数
     */
    public static void solution(int T, int[] array_n, List<Integer[][]> list_xy) {
        //组数
        for (int i = 1; i <= T; i++) {
            //对每组进行判断
            //物品个数，从中尝试每次取出 k 个
            int n = array_n[i - 1];
            //从第2个到第n个取 2 ... n 组的每个情况都要考虑
            Integer[][] xy = list_xy.get(i - 1);//每个物品对应的 x 和 y 属性，0 是 x 数组，1 是 y 数组。
            int sum = getSum(n, xy);
            System.out.println(sum);
        }
    }

    public static int getSum(int n, Integer[][] xy) {
        Integer[] arr = new Integer[n];
        //初始化
        for (int j = 0; j < arr.length; j++) {
            arr[j] = j;
        }
        for (int k = n; k > 1; k--) {
            List<List<Integer>> temp = new ArrayList<>();
            combine(0, k, arr, temp);
            for (List<Integer> t : temp) {
                if (judge(t, xy)) {
                    return t.size();
                }
            }
        }
        return 1;
    }

    /**
     * 递归函数
     *
     * @param index 索引号
     * @param k     一次取几个数
     * @param arr   所有的数
     * @param temp
     */
    public static void combine(Integer index, Integer k, Integer[] arr, List<List<Integer>> temp) {
        if (k == 1) {
            for (int i = index; i < arr.length; i++) {
                tmpArr.add(arr[i]);
                //重新开辟内存空间存储，否则会将其值改变
                List<Integer> other = new ArrayList<>();
                for (Integer integer : tmpArr) {
                    other.add(integer);
                }
                temp.add(other);
                tmpArr.remove(arr[i]);
            }
        } else if (k > 1) {
            for (int i = index; i <= arr.length - k; i++) {
                tmpArr.add(arr[i]);
                combine(i + 1, k - 1, arr, temp);
                tmpArr.remove(arr[i]);
            }
        } else {
            return;
        }
    }

    public static boolean judge(List<Integer> tmpArr, Integer[][] xy) {
        for (int i = 0; i < tmpArr.size(); i++) {
            int x = tmpArr.get(i);
            for (int j = i + 1; i < tmpArr.size(); i++) {
                int y = tmpArr.get(j);
                if (!((xy[0][x] > xy[0][y] && xy[0][x] > xy[0][y]) || (xy[1][x] > xy[1][y] && xy[1][x] > xy[1][y]))) {
                    return false;
                }
            }
        }
        return true;
    }
}
